Dive into Algorithms by Bradford Tuckfield

Author:Bradford Tuckfield [Tuckfield, Bradford]
Language: eng
Format: epub, mobi
ISBN: 9781718500693
Published: 2020-11-17T00:00:00+00:00

Implementing Nearest Neighbor Search

We’ll start by writing a function that can find the nearest neighbor of any given city. Suppose that we have a point called point and a list of cities called cities. The distance between point and the jth element of cities is given by the following Pythagorean-style formula:

point = [0.5,0.5] j = 10 distance = math.sqrt((point[0] - cities[j][0])**2 + (point[1] - cities[j][1])**2)

If we want to find which element of cities is closest to our point (the point’s nearest neighbor), we need to iterate over every element of cities and check the distance between the point and every city, as in Listing 6-1.

def findnearest(cities,idx,nnitinerary): point = cities[idx] mindistance = float('inf') minidx = - 1 for j in range(0,len(cities)): distance = math.sqrt((point[0] - cities[j][0])**2 + (point[1] - cities[j][1])**2) if distance < mindistance and distance > 0 and j not in nnitinerary: mindistance = distance minidx = j return(minidx)

Listing 6-1: The findnearest() function, which finds the nearest city to a given city

After we have this findnearest() function, we’re ready to implement the nearest neighbor algorithm. Our goal is to create an itinerary called nnitinerary. We’ll start by saying that the first city in cities is where our salesman starts:

nnitinerary = [0]

If our itinerary needs to have N cities, our goal is to iterate over all the numbers between 0 and N – 1, find for each of those numbers the nearest neighbor to the most recent city we visited, and append that city to our itinerary. We’ll accomplish that with the function in Listing 6-2, donn() (short for “do nearest neighbor”). It starts with the first city in cities, and at every step adds the closest city to the most recently added city until every city has been added to the itinerary.

def donn(cities,N): nnitinerary = [0] for j in range(0,N - 1): next = findnearest(cities,nnitinerary[len(nnitinerary) - 1],nnitinerary) nnitinerary.append(next) return(nnitinerary)

Listing 6-2: A function that successively finds the nearest neighbor to each city and returns a complete itinerary

We already have everything we need to check the performance of the nearest neighbor algorithm. First, we can plot the nearest neighbor itinerary:

plotitinerary(cities,donn(cities,N),'TSP - Nearest Neighbor','figure3')

Figure 6-3 shows the result we get.

Figure 6-3: The itinerary generated by the nearest neighbor algorithm

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.